//
// Created by Senhai Xu on 2025/3/5.
//
//二叉树
#include<iostream>
template <typename T>
class TreeNode{
public:
    T data;
    TreeNode<T>* left;
    TreeNode<T>* right;
//    构造函数
    TreeNode(int val): data(val), left(nullptr), right(nullptr){
    }
};

template <typename T>
class BinaryTree{
private:
    TreeNode<T>* root;
//    插入辅助函数
    TreeNode<T>*  insertRecursive(TreeNode<T>* node, int val){
        if(node== nullptr){
            return new TreeNode<T>(val);
        }
        if(val < node->data){
            node->left = insertRecursive(node->left, val);
        }else if(val > node->data){
            node->right = insertRecursive(node->right, val);
        }
        return node;
    };
//    先序遍历（根左右）辅助函数
    void preOrderRecursive(TreeNode<T>* node){
        if(node!= nullptr){
            std::cout<<node->data<<" ";
            preOrderRecursive(node->left);
            preOrderRecursive(node->right);
        }
    };
//    中序遍历（左根右）辅助函数
    void inOrderRecursive(TreeNode<T>* node){
        if(node!= nullptr){
            inOrderRecursive(node->left);
            std::cout<<node->data<<" ";
            inOrderRecursive(node->right);
        }
    };
//    后序遍历（左右根）辅助函数
    void postOrderRecursive(TreeNode<T>* node){
        if(node!= nullptr){
            postOrderRecursive(node->left);
            postOrderRecursive(node->right);
            std::cout<<node->data<<" ";
        }
    };
//    释放内存
    void destroyTree(TreeNode<T>* node){
        if(node!= nullptr){
            destroyTree(node->left);
            destroyTree(node->right);
            delete node;
        }
    };
public:
    BinaryTree(): root(nullptr){
    }
    ~BinaryTree(){
        destroyTree(root);
    }
    // 插入节点
    void insert(T value) {
        root = insertRecursive(root, value);
    }

// 前序遍历
    void preOrderTraversal() {
        preOrderRecursive(root);
        std::cout << std::endl;
    }

    // 中序遍历
    void inOrderTraversal() {
        inOrderRecursive(root);
        std::cout << std::endl;
    }

    // 后序遍历
    void postOrderTraversal() {
        postOrderRecursive(root);
        std::cout << std::endl;
    }

};

int main(){
    BinaryTree<int> tree;
    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(2);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);

    std::cout << "Pre-order traversal: ";
    tree.preOrderTraversal();

    std::cout << "In-order traversal: ";
    tree.inOrderTraversal();

    std::cout << "Post-order traversal: ";
    tree.postOrderTraversal();

    return 0;


}

//二叉搜索树

//红黑树